RPS - Nierówności probabilistyczne - zadania

Zad. 1. Kolekcjoner kuponów c.d. Obliczyć p-stwo tego, że w zadaniu z kolekcjonerem kuponow będziemy potrzebować ponad 2*n*ln(n) prób. (a) z nier. markowa (b) z nier. czebyszewa (c) na palcach Ćw. 9.1. Zad. 2. Mamy algorytm RANDOMIZOWANY, rozwiązujący pewien minimalizacyjny problem optymalizacyjny, tj. szuka rozwiązania o najmniejszym koszcie. Przypuśćmy, że potrafimy przeanalizować nasz algorytm i znamy wart. ocz. kosztu rozwiązania mu. Załóżmy też, że satysfakcjonuje nas rozwiązanie o koszcie 2*mu (albo c*mu dla jakiegoś c > 1). Jak znaleźć takie rozwiazanie z dużym p-stwem? Ćw. 9.2. Zad. 3. Mamy algorytm RANDOMIZOWANY, który oblicza interesująca nas wielkość. Wartość oczekiwana wyniku zwracanego przez algorytm mu jest równa faktycznej wartości, a odchylenie standardowe wynosi sigma. Jak z dużym prawdopodobieństwem uzyskać wynik w przedziale (mu-delta,mu+delta)? Ćw. 8.3. + Z.d. 8.1. Zad. 4. Robimy sondaz przedwyborczy. Jest dwóch kandydatów: A i B, pytamy n osób na kogo głosują. Każda z osób niezależnie odpowiada A lub B, przy czym zakładamy, że sondażowana próbka jest reprezentatywna (tzn. p-stwo tego, że sondażowana osoba odpowie A jest równe frakcji osób popierających A). Chcemy się dowiedzieć ile osób popiera kandydata A? Oszacować jak duże powinno być n, żeby p-stwo popełnienia błędu w sondażu o więcej niż 1% było mniejsze niż 5%: (a) z nier. Czebyszewa (b) z centralnego twierdzenia granicznego (c) z nier. Chernoffa? Wskazówka: Interesuje nas n, dla którego P( |X-p_A| >= 0.01 ) <= 0.05. Z.d. 9.1.